package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

import java.util.Stack;

/**
 * @author Dennis Li
 * @date 2020/10/20 22:04
 */
public class ReorderList_143 {
    public void reorderList(ListNode head) {
        if (head == null) return;
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        cur = head;
        int size = stack.size(), count = 0;
        while (count++ < size / 2) {
            ListNode node = stack.pop();
            node.next = cur.next;
            cur.next = node;
            cur = cur.next.next;
        }
        cur.next = null;
    }

    static class Solution {
        public void reorderList(ListNode head) {
            if (head == null || head.next == null) return;
            ListNode fast = head, slow = head;

            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode l1 = head, l2 = slow.next;
            slow.next = null;

            while (l1 != null && l2 != null) {
                ListNode next1 = l1.next, next2 = l2.next;
                l1.next = l2;
                l1 = next1;
                l2.next = l1;
                l2 = next2;
            }

        }

        public ListNode reverse(ListNode head) {
            if (head.next == null) {
                return head;
            }
            ListNode node = reverse(head.next);
            node.next = head;
            head.next = null;
            return node;
        }

    }

}
